package lc.q51_100;

public class Q60 {
    public String getPermutation(int n, int k) {
        if (n == 0) {
            return "";
        }
        if (n == 1) {
            return "1";
        }
        // 最简单的就是一个个排，但是肯定不合理
        // 求n-1!的大小得到
        int[] maxs = new int[n];
        maxs[0] = 1;
        for (int i = 1; i < n; i++) {
            maxs[i] = (i + 1) * maxs[i-1];
        }
        // 那么第一位应该是？
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = n-1; i > 0; i--) {
            int l = (k-1) / maxs[i-1];
            // 将nums[l]移动到最后，然后后面的数移动到前面
            sb.append(nums[l]);
            // l开始之后的数字+1
            for (int j = l; j < i && j < n; j++) {
                nums[j] = nums[j+1];
            }
            k = k - l * maxs[i-1];
        }
        // 添加最后一个数
        sb.append(nums[(k-1) / maxs[0]]);
        return sb.toString();
    }

    public static void main(String[] args) {
        final Q60 q60 = new Q60();
        final String permutation = q60.getPermutation(4, 9);
        System.out.println(permutation);
    }
}
